home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gsnogc.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  9.9 KB  |  352 lines
  1. /* Copyright (C) 1996, 2000 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gsnogc.c,v 1.5 2000/09/22 04:17:52 lpd Exp $ */
  20. /* String freelist implementation and ersatz garbage collector */
  21. #include "gx.h"
  22. #include "gsmdebug.h"
  23. #include "gsnogc.h"
  24. #include "gsstruct.h"
  25. #include "gxalloc.h"
  26.  
  27. /*
  28.  * We implement string freelists here, because they are only useful
  29.  * in non-garbage-collected environments.
  30.  */
  31.  
  32. /*
  33.  * Get and put unaligned 32-bit values.  NOTE: these procedures must match
  34.  * the value of SFREE_NB defined in gxalloc.h.
  35.  */
  36. #define NB SFREE_NB
  37. #if NB == 4
  38. private uint
  39. get_uu32(const byte *ptr)
  40. {
  41.     return (ptr[0] << 24) + (ptr[1] << 16) + (ptr[2] << 8) + ptr[3];
  42. }
  43. private void
  44. put_uu32(byte *ptr, uint val)
  45. {
  46.     ptr[0] = val >> 24;
  47.     ptr[1] = (byte)(val >> 16);
  48.     ptr[2] = (byte)(val >> 8);
  49.     ptr[3] = (byte)val;
  50. }
  51. #endif /* otherwise, undefined procedures will give an error */
  52.  
  53. /* Allocate a string. */
  54. /* Scan the current chunk's free list if the request is large enough. */
  55. /* Currently we require an exact match of the block size. */
  56. private byte *
  57. sf_alloc_string(gs_memory_t * mem, uint nbytes, client_name_t cname)
  58. {
  59.     gs_ref_memory_t * const imem = (gs_ref_memory_t *)mem;
  60.  
  61.     if (nbytes >= 40 && nbytes < imem->large_size) {
  62.     byte *base = csbase(&imem->cc);
  63.     byte *prev = 0;
  64.     uint offset = imem->cc.sfree;
  65.     uint next;
  66.     byte *ptr;
  67.  
  68.     for (; offset != 0; prev = ptr, offset = next) {
  69.         ptr = base + offset;
  70.         next = get_uu32(ptr + NB);
  71.         if (get_uu32(ptr) != nbytes)
  72.         continue;
  73.         /* Take this block. */
  74.         if (prev == 0)
  75.         imem->cc.sfree = next;
  76.         else
  77.         put_uu32(prev + NB, next);
  78.         if_debug4('A', "[a%d:+>F]%s(%u) = 0x%lx\n", imem->space,
  79.               client_name_string(cname), nbytes, (ulong) ptr);
  80.         gs_alloc_fill(ptr, gs_alloc_fill_alloc, nbytes);
  81.         imem->lost.strings -= nbytes;
  82.         return ptr;
  83.     }
  84.     }
  85.     return (*gs_ref_memory_procs.alloc_string) (mem, nbytes, cname);
  86. }
  87.  
  88. /* Free a string. */
  89. private void
  90. sf_free_string(gs_memory_t * mem, byte * str, uint size, client_name_t cname)
  91. {
  92.     gs_ref_memory_t * const imem = (gs_ref_memory_t *)mem;
  93.     chunk_t *cp;
  94.     uint str_offset;
  95.  
  96.     if (str == imem->cc.ctop) {
  97.     if_debug4('A', "[a%d:-> ]%s(%u) 0x%lx\n", imem->space,
  98.           client_name_string(cname), size, (ulong) str);
  99.     imem->cc.ctop += size;
  100.     gs_alloc_fill(str, gs_alloc_fill_free, size);
  101.     return;
  102.     }
  103.     if_debug4('A', "[a%d:->#]%s(%u) 0x%lx\n", imem->space,
  104.           client_name_string(cname), size, (ulong) str);
  105.     imem->lost.strings += size;
  106.     if (ptr_is_in_chunk(str, &imem->cc)) {
  107.     cp = &imem->cc;
  108.     /* We already tested for the string being at ctop. */
  109.     } else {
  110.     chunk_locator_t loc;
  111.  
  112.     loc.memory = imem;
  113.     loc.cp = imem->clast;
  114.     if (!chunk_locate_ptr(str, &loc))
  115.         return;        /* something is probably wrong.... */
  116.     cp = loc.cp;
  117.     if (str == cp->ctop) {
  118.         cp->ctop += size;
  119.         return;
  120.     }
  121.     }
  122.     str_offset = str - csbase(cp);
  123.     if (size >= 2 * NB) {
  124.     byte *prev;
  125.     uint next;
  126.  
  127.     put_uu32(str, size);
  128.     if (cp->sfree == 0 || str_offset < cp->sfree) {
  129.         /* Put the string at the head of the free list. */
  130.         put_uu32(str + NB, cp->sfree);
  131.         cp->sfree = str_offset;
  132.         return;
  133.     }
  134.     /* Insert the new string in address order. */
  135.     prev = csbase(cp) + cp->sfree;
  136. #ifdef DEBUG
  137.     if (gs_debug_c('?')) {
  138.         if (prev < str + size && prev + get_uu32(prev) > str) {
  139.         lprintf4("freeing string 0x%lx(%u), overlaps 0x%lx(%u)!\n",
  140.              (ulong) str, size, (ulong) prev, get_uu32(prev));
  141.         return;
  142.         }
  143.     }
  144. #endif
  145.     for (;;) {
  146.         next = get_uu32(prev + NB);
  147. #ifdef DEBUG
  148.         if (gs_debug_c('?') && next != 0) {
  149.         byte *pnext = csbase(cp) + next;
  150.  
  151.         if (pnext < str + size && pnext + get_uu32(pnext) > str) {
  152.             lprintf4("freeing string 0x%lx(%u), overlaps 0x%lx(%u)!\n",
  153.                  (ulong) str, size, (ulong) pnext, get_uu32(pnext));
  154.             return;
  155.         }
  156.         }
  157. #endif
  158.         if (next >= str_offset || next == 0)
  159.         break;
  160.         prev = csbase(cp) + next;
  161.     }
  162.     put_uu32(str + NB, next);
  163.     put_uu32(prev + NB, str_offset);
  164.     gs_alloc_fill(str + 2 * NB, gs_alloc_fill_free, size - 2 * NB);
  165.     } else {
  166.     /*
  167.      * Insert the string in the 1-byte free list(s).  Note that
  168.      * if it straddles a 256-byte block, we need to do this twice.
  169.      */
  170.     uint *pfree1 = &cp->sfree1[str_offset >> 8];
  171.     uint count = size;
  172.     byte *prev;
  173.     byte *ptr;
  174.  
  175.     if (*pfree1 == 0) {
  176.         *str = 0;
  177.         *pfree1 = str_offset;
  178.         if (!--count)
  179.         return;
  180.         prev = str;
  181.         ptr = str + 1;
  182.     } else if (str_offset < *pfree1) {
  183.         *str = *pfree1 - str_offset;
  184.         *pfree1 = str_offset;
  185.         if (!--count)
  186.         return;
  187.         prev = str;
  188.         ptr = str + 1;
  189.     } else {
  190.         uint next;
  191.  
  192.         prev = csbase(cp) + *pfree1;
  193.         while ((next = *prev) != 0 && prev + next < str)
  194.         prev += next;
  195.         ptr = str;
  196.     }
  197.     for (;;) {
  198.         /*
  199.          * Invariants:
  200.          *      ptr == str + size - count
  201.          *      prev < sfbase + str_offset
  202.          *      *prev == 0 || prev + *prev > sfbase + str_offset
  203.          */
  204.         *ptr = (*prev == 0 ? 0 : prev + *prev - ptr);
  205.         *prev = ptr - prev;
  206.         if (!--count)
  207.         break;
  208.         prev = ptr++;
  209.         if (!(++str_offset & 255)) {
  210.         /* Move to the next block of 256 bytes. */
  211.         ++pfree1;
  212.         *ptr = (byte) * pfree1;
  213.         *pfree1 = str_offset;
  214.         if (!--count)
  215.             break;
  216.         prev = ptr++;
  217.         ++str_offset;
  218.         }
  219.     }
  220.     }
  221. }
  222.  
  223. /* Enable or disable freeing. */
  224. private void
  225. sf_enable_free(gs_memory_t * mem, bool enable)
  226. {
  227.     (*gs_ref_memory_procs.enable_free) (mem, enable);
  228.     if (enable)
  229.     mem->procs.free_string = sf_free_string;
  230. }
  231.  
  232. /* Merge free strings at the bottom of a chunk's string storage. */
  233. private void
  234. sf_merge_strings(chunk_t * cp)
  235. {
  236.     for (;;) {
  237.     byte *ctop = cp->ctop;
  238.     uint top_offset = ctop - csbase(cp);
  239.     uint *pfree1;
  240.  
  241.     if (cp->sfree == top_offset) {    /* Merge a large free block. */
  242.         cp->sfree = get_uu32(ctop + NB);
  243.         cp->ctop += get_uu32(ctop);
  244.         continue;
  245.     }
  246.     if (!cp->sfree1)
  247.         break;
  248.     pfree1 = &cp->sfree1[top_offset >> 8];
  249.     if (*pfree1 != top_offset)
  250.         break;
  251.     /* Merge a small (1-byte) free block. */
  252.     *pfree1 = (*ctop ? *pfree1 + *ctop : 0);
  253.     cp->ctop++;
  254.     }
  255. }
  256.  
  257. /* Consolidate free space. */
  258. private void
  259. sf_consolidate_free(gs_memory_t *mem)
  260. {
  261.     gs_ref_memory_t *imem = (gs_ref_memory_t *)mem;
  262.     chunk_t *cp;
  263.  
  264.     alloc_close_chunk(imem);
  265.     for (cp = imem->clast; cp != 0; cp = cp->cprev) {
  266.     byte *top = cp->ctop;
  267.  
  268.     sf_merge_strings(cp);
  269.     imem->lost.strings -= cp->ctop - top;
  270.         if (cp->ctop == cp->climit && cp->smark_size != 0) {
  271.         /*
  272.          * No string space is being used.  Since we are not using the
  273.          * 'string marking table' for GC, we can recover its space by
  274.          * deleting the smark area, setting smark_size = 0, and sliding
  275.          * up ctop and climit.  We also need to recompute the size of
  276.          * the string freelist area (it will be larger, since the
  277.          * space potentially allocated to strings is larger).
  278.          */
  279.         cp->smark_size = 0;
  280.         cp->smark = 0;
  281.         /*
  282.          * Reserve enough space for the string freelist all the way to
  283.          * cend even though the climit will be moved to before the
  284.          * freelist area.  This recovers most of the space.
  285.          */
  286.         cp->climit = cp->cend;
  287.         cp->climit -= STRING_FREELIST_SPACE(cp);
  288.         cp->ctop = cp->climit;
  289.         alloc_init_free_strings(cp);
  290.     }
  291.     }
  292.     alloc_open_chunk(imem);
  293.  
  294.     /* Merge free objects, detecting entirely free chunks. */
  295.     ialloc_consolidate_free(imem);
  296. }
  297.  
  298. /*
  299.  * This procedure has the same API as the garbage collector used by the
  300.  * PostScript interpreter, but it is designed to be used in environments
  301.  * that don't need garbage collection and don't use save/restore.  All it
  302.  * does is coalesce free blocks at the high end of the object area of each
  303.  * chunk, and free strings at the low end of the string area, and then if
  304.  * not 'controlled' memory, free completely empty chunks.
  305.  *
  306.  * Note that any string marking area will be added to the free space
  307.  * within the chunk if possible.
  308.  */
  309.  
  310. private void use_string_freelists(P1(gs_ref_memory_t *mem));
  311. void
  312. gs_nogc_reclaim(vm_spaces * pspaces, bool global)
  313. {
  314.     int space;
  315.     gs_ref_memory_t *mem_prev = 0;
  316.  
  317.     for (space = 0; space < countof(pspaces->memories.indexed); ++space) {
  318.     gs_ref_memory_t *mem = pspaces->memories.indexed[space];
  319.  
  320.     if (mem == 0 || mem == mem_prev)
  321.         continue;
  322.     mem_prev = mem;
  323.     use_string_freelists(mem);
  324.     if (mem->stable_memory != (gs_memory_t *)mem &&
  325.         mem->stable_memory != 0
  326.         )
  327.         use_string_freelists((gs_ref_memory_t *)mem->stable_memory);
  328.     }
  329. }
  330. private void
  331. use_string_freelists(gs_ref_memory_t *rmem)
  332. {
  333.     /*
  334.      * ANSI made an incompatible change to the C language standard that
  335.      * caused the following to generate aliasing warnings:
  336.     gs_memory_t *mem = (gs_memory_t *)rmem;
  337.      * Consequently, we now use rmem rather than mem in the assignments
  338.      * below, even though this degrades code readability by obscuring the
  339.      * fact that they are only manipulating fields of the more abstract
  340.      * superclass.
  341.      */
  342.     /* Change the allocator to use string freelists in the future.  */
  343.     rmem->procs.alloc_string = sf_alloc_string;
  344.     if (rmem->procs.free_string != gs_ignore_free_string)
  345.     rmem->procs.free_string = sf_free_string;
  346.     rmem->procs.enable_free = sf_enable_free;
  347.     rmem->procs.consolidate_free = sf_consolidate_free;
  348.  
  349.     /* Merge free objects, detecting entirely free chunks. */
  350.     gs_consolidate_free((gs_memory_t *)rmem);
  351. }
  352.